package srcInterviewPrep;

import java.util.ArrayList;
import java.util.List;

public final class TernaryTree
{
    private static final class Node
    {
        private int value;
        private Node left;
        private Node right;
        private List<Integer> equalItems;

        public Node(int value)
        {
            this.value = value;
            this.equalItems = new ArrayList<Integer>();
        }
    }

    private Node root;

    public void Insert(int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return;
        }

        InsertFromNode(root, value);
    }

    private static void InsertFromNode(Node node, int value)
    {
        if (value == node.value)
        {
            node.equalItems.add(value);
            return;
        }

        if (value < node.value)
        {
            if (node.left == null)
            {
                node.left = new Node(value);
                return;
            }

            InsertFromNode(node.left, value);
        }
        else
        {
            if (node.right == null)
            {
                node.right = new Node(value);
                return;
            }

            InsertFromNode(node.right, value);
        }
    }

    public void Delete(int value)
    {
        if (root == null)
        {
            return;
        }

        root = DeleteFromNode(root, value);
    }

    private static Node DeleteFromNode(Node node, int value)
    {
        if (node.value == value)
        {
            if(!node.equalItems.isEmpty())
            {
                node.equalItems.remove(0);
                return node;
            }

            node = DeleteNode(node);
            return node;
        }

        if (value < node.value)
        {
            if (node.left == null)
            {
                return node;
            }

            node.left = DeleteFromNode(node.left, value);
            return node;
        }

        if (node.right == null)
        {
            return node;
        }

        node.right = DeleteFromNode(node.right, value);
        return node;
    }

    private static Node DeleteNode(Node node)
    {
        if (node.left == null
            && node.right == null)
        {
            return null;
        }

        if (node.left == null)
        {
            return node.right;
        }

        if (node.right == null)
        {
            return node.left;
        }

        int v = GetSuccessorValue(node.right);
        node.value = v;

        DeleteSuccessor(node.right);
        return node;
    }

    private static int GetSuccessorValue(Node node)
    {
        if (node.left == null)
        {
            return node.value;
        }

        return GetSuccessorValue(node.left);
    }

    private static Node DeleteSuccessor(Node node)
    {
        if (node.left == null)
        {
            return null;
        }

        node.left = DeleteSuccessor(node.left);
        return node;
    }

    public void PrintPreOrderTraversal()
    {
        PrintPreOrderTraversalFromNode(root);
        System.out.println();
    }

    private static void PrintPreOrderTraversalFromNode(Node node)
    {
        if (node == null)
        {
            return;
        }

        System.out.print(node.value);
        System.out.print(' ');
        for (Integer i : node.equalItems)
        {
            System.out.print(i);
            System.out.print(' ');
        }

        PrintPreOrderTraversalFromNode(node.left);
        PrintPreOrderTraversalFromNode(node.right);
    }
}
